/*
 * Copyright (c) 2021
 * User:Administrator
 * File:翻转二叉树.java
 * Date:2021/02/21 17:56:21
 */

package com.mlamp.二叉树;

import java.util.*;

/**
 * 翻转一棵二叉树。
 */
public class 翻转二叉树 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);

        翻转二叉树 instance = new 翻转二叉树();
        List<String> strings = instance.levelTraversal(root);
        instance.printList(strings);
        TreeNode transfer = instance.transfer(root);
        strings = instance.levelTraversal(transfer);
        instance.printList(strings);

        TreeNode treeNode = instance.transfer2(transfer);
        strings = instance.levelTraversal(treeNode);
        instance.printList(strings);


        System.out.println("\n");
        TreeNode invertTreeNode = instance.invertTree(treeNode);
        strings = instance.levelTraversal(invertTreeNode);
        instance.printList(strings);


    }

    private void printList(List<String> inputs) {
        if (inputs == null || inputs.isEmpty()) return;
        for (String line : inputs) {
            System.out.println(line);
        }
    }

    private static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    public TreeNode transfer(TreeNode root) {
        //后续遍历
        if (root == null) return root;
        transfer(root.left);
        transfer(root.right);
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }

    public TreeNode transfer2(TreeNode root) {
        //后续遍历
        if (root == null) return root;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        transfer(root.left);
        transfer(root.right);
        return root;
    }


    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode tmp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(tmp);
        return root;
    }


    public List<String> levelTraversal(TreeNode root) {
        if (root == null) Collections.emptyList();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<String> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            StringBuilder sb = new StringBuilder();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);
                sb.append(poll.value).append(" ");
            }
            res.add(sb.toString());
        }
        return res;
    }
}
